Interconnect routing is a process of determining the wires needed to connect sets of terminals in a circuit. Each set of terminals is defined as a net, or network, and is composed of a source, or driver, and one or more sinks. Wires are defined so that all terminals of the same net become electrically equivalent. Global routing is a process of determining the net routing topology, which forms a tree structure, or a connected acyclic graph. Special nodes termed Steiner nodes are introduced by the router to create branching points for wires in such a way that the route meets the desired goals. A routing tree with Steiner nodes is referred to as a Steiner tree. It is well known that algorithms for determining minimum-length Steiner trees are very difficult and fall into the NP-Hard class of problems, see for example, M. R. Garey et al., “The Rectilinear Steiner Tree is NP-Complete,” SIAM Journal on Applied Mathematics, Vol. 32, No. 4, 1977, pp. 826-834.
A critical sink of a net is one for which the time taken for a signal to travel from the source to that sink is to be minimized. All other sinks are considered non-critical. In conventional routing, there is no differentiation between critical and non-critical sinks. Instead, the goal is simply to minimize the total wire length. In timing driven routing, the goal is to minimize the time taken for a signal to traverse from the source to critical sinks and, as a secondary goal, minimize the total wire length connecting all the non-critical sinks.
Typically the time taken for a signal to reach a particular sink from the source is determined by the total wire length of the wiring as well as the route from the source to the sink under consideration. It is desirable that the total capacitance of wires connected to the wire from source to critical sink be minimized, while the total wiring of the entire route to be minimized. However, these two requirements are often conflicting.
As feature sizes decrease with scaling, interconnect delays play an ever increasing role in determining the performance of a VLSI design. Routers in today's designs require timing awareness to optimize interconnect delays to critical sinks. In order to effectively use interconnect delays during logic optimization, those algorithms utilized to generate minimal Rectilinear Steiner Routing Trees (RSRTs) must be very fast. To ensure similarity between routes generated during the final routing phase and the wiring estimates used by the logic and placement optimizations, it is important that wiring estimates used in the early stages of design mimic wiring data obtained from the final routing. It is therefore desirable that the same algorithms be used in both cases.
Due to varying design requirements, different nets may require different routing strategies. Minimizing wire delays often leads to solutions with direct paths from source to critical sinks that are not shared with other sinks. This is usually in direct conflict with the goal of minimizing total wire length. It is essential for routers to have the capacity to avoid blockages which could be layout obstacles or hard cores. Congestion mitigation is another important factor that also needs to be addressed by these Steiner tree algorithms. Such requirements coupled with timing considerations stress RSRT algorithms to their limits.
Most routers utilized in the early stages of design use a skeletal tree. See, for example, C. J. Alpert et al., “Fast and Flexible Buffer Trees that Navigate the Physical Layout Environment,” Proc. of the 41st DAC, June 7-11, pp. 24-29; C. J. Alpert et al., “Prim-Jijkstra Tradeoffs for Improved Performance-Driven Routing Tree Design,” IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, Vol. 14, No. 7, July 1995, pp. 890-896; K. D. Boese et al., “Near Optimal Critical Sink Routing,” IEEE Trans. On Computer-Aided Design of integrated Circuits and Systems, Vol. 14, No. 12, July 1995, pp. 1417-1436; M. Borah et al., “An Edge Based Heuristic for Steiner Routing,” IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, Vol. 13, No. 12, July 1994, pp. 1563-1568; J. Cong et al., “Efficient Algorithms for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design,” IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems,” Vol. 17, Iss. 1, January 1998, pp. 24-39; J. Cong et al., “Provably Good Performance Driven Routing,” IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, Vol. 11, No. 6, 1992, 732-752; M. Hanan, “On Steiner's Problem with Rectilinear Distance,” SIAM Journal on Applied Mathematics,” Vol. 30, 2976, pp. 255-265; J.-M. Ho et al., “New Algorithms for the Rectilinear Steiner Tree Problem,” IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, Vol. 9, No. 2, February 1990, pp. 185-193; X. Hong et al., “Performance-Driven Steiner Tree Algorithms for Global Routing,” Proc. of the 30th DAC, Jun. 14-18, 1993, pp. 177-181; and F. K. Hwang et al., “The Steiner Tree Problem,” Annals of Discrete Mathematics, Vol. 53, Elsevier Science Publishers, Netherlands, 1992. These algorithms are dependent on the method used to generate the skeleton and lack the flexibility of maze routers.
On the other hand maze routers are either too time consuming or are not timing aware. See, for example, S.-W. Hur et al., “Timing-driven Maze Routing,” IEEE Trans. On Computer-Aided Design of Integrated Circuit s and Systems, Vol. 19, No. 2, February 2000, pp. 234-241; S. Prasitjutrakul et al., “A Timing-Driven Global Router for Custom Chip Design,” Proc. of the Int. Conf. on Computer-Aided Design, Nov. 11-15, 1990, pp. 48-51; and K. Suzuki et al., “A Hardware Maze Router with Application to Interactive Rip-Up and Reroute,” IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, Vol. 5, No. 4, October 1986, pp. 466-476.
Thus, it would be highly desirable to be able to provide flexible timing-driven routing trees that provide effective tradeoffs between wire length and timing.